#include <bits/stdc++.h>

using namespace std;

// 二叉树的锯齿形层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

// 不需要提交这个类
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution 
{
private:
    static const int MAXN = 2001;
    TreeNode* queue[MAXN];
    int l, r;

public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        if(root == nullptr) return {};
        
        l = r = 0;
        queue[r++] = root;
        // false 代表从左往右
        // true 代表从右往左
        bool reverse = false;
        vector<vector<int>> ans;
        while(l < r)
        {
            int n = r - l;
            vector<int> v;
            // reverse == false, 左 -> 右， l....r-1, 收集size个
            // reverse == true,  右 -> 左， r-1....l, 收集size个
            // 左 -> 右, i = i + 1
            // 右 -> 左, i = i - 1
            for(int i = reverse ? r - 1 : l, j = reverse ? -1 : 1, k = 0; k < n; i += j, ++k)
            {
                TreeNode* cur = queue[i];
                v.emplace_back(cur->val);
            }
            for(int i = 0; i < n; ++i)
            {
                TreeNode* cur = queue[l++];
                if(cur->left) queue[r++] = cur->left;
                if(cur->right) queue[r++] = cur->right;
            }

            ans.emplace_back(v);
            reverse = !reverse;
        }

        return ans; 
    }
};


class Solution 
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        if(root == nullptr) return {};
        
        vector<vector<int>> ret;
        queue<TreeNode*> q;
        q.push(root);
        bool isLeft = true;
        while(!q.empty())
        {
            int n = q.size();
            vector<int> tmp;
            for(int i = 0; i < n; ++i)
            {
                TreeNode* t = q.front();
                q.pop();
                tmp.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }

            if(!isLeft) reverse(tmp.begin(), tmp.end());
            isLeft = !isLeft;
            ret.push_back(tmp);
        }

        return ret;
    }
};